Persistent Segment Tree
Operations
モノイド$ Mの列$ (a_1, a_2, \dots, a_n)を扱う.
$ \mathtt{new}()
列の項がすべて$ Mの単位元であるSegment Treeを作成する.
時間計算量$ \Theta(n)
$ \mathtt{build}(a_1, a_2, \dots, a_n)
与えられた列を表現するSegment Treeを作成する.
時間計算量$ \Theta(n)
$ \mathtt{set}(i, x)
$ a_iに$ xを代入したSegment Treeを作成する.
時間計算量$ \Omicron(\log n) 空間計算量$ \Theta(\log n)
$ \mathtt{fold}(l, r)
$ a_l \cdot a_{l+1} \cdot \dots \cdot a_rを計算する.
時間計算量$ \Omicron(\log n)
Summary
setで値を更新するノードを新しく作る
set($ 3, x)
https://gyazo.com/8b0d97c9f61c28f2fa429a15034452fc
setする前のSegment Treeは黒い根
https://gyazo.com/48a297a01231a3a16bc6256577ae476e
setした後のSegment Treeは赤い根
https://gyazo.com/b46a0dbed599a64aa603fd7bd5ffbfaa
更新箇所が$ \log_2 n
References
Notes
C++11以降で書くならshared_ptr
Implementations
Problems
imos法